00100	SYLLABUS FOR THE QUALIFYING EXAMINATION IN ARTIFICIAL INTELLIGENCE
00200	
00300	Computer Science Department, Stanford University, November, 1969
00400	
00500	
00600		The subject of artificial intelligence may be regarded as
00700	divided into four sub-topics: heuristics, perception and control,
00800	semantic information processing, and representation theory.  The
00900	examination will have questions in all four areas with some emphasis
01000	on heuristics which is the best developed of the four.  We have
01100	classified the descriptions and references into the separate groups, although most
01200	artificial intelligence work combines ideas from several subareas.
01300	
01400	
01500		1.  Heuristics.  This is the problem of search of large spaces
01600	of alternatives for some particular kind of information.  The best
01700	developed examples are: Game playing programs search the move tree of
01800	a game in order to determine the best move.  Theorem proving programs
01900	search spaces of sentences in order to find proofs of theorems.  Dendral
02000	searches spaces of chemical structures in order to find one that
02100	satisfies conditions of mass spectra.  The student is expected to have
02200	a specific familiarity with the state of the art in theorem proving and
02300	game playing.  Besides that he should be familiar with the general
02400	discussions of heuristic search in 5.  The examiners are aware that all
02500	these discussions are limited in scope and that there does not yet exist
02600	a systematic theory of heuristics nor is there even a single source that
02700	summarizes what is known.  Questions that require the student to go
02800	beyond published material in discussing current issues may be included.
02900	
03000		You may be asked a short program to express some heuristic procedure.
03100	An acquaintance with Micro-planner and LISP is recommended, since these
03150	languages are likely to be appropriate, but any well-known language may be
03175	used.
03200	
03300		2  Perception and Control.  Work in perception has taken two main
03400	directions: classification and description.  Classification is the older
03500	problem and involves making the computer put patterns into categories
03600	corresponding to letters of the alphabet, spoken words from a fixed
03700	vocabulary, etc.  This field is not much emphasized in the Stanford Computer
03800	Science Department and the student will not be held responsible for this
03900	material.
04000	
04100		The problem of describing stimuli so as to be able to take some
04200	action has received greater emphasis in our department.  Examples of
04300	this are visual scene description for the purpose of redisplay of
04400	selected information, for the purpose of picking up blocks or constructing
04500	a tower, or the description of a road scene for the purpose of driving a
04600	vehicle.  The related problem of the description of connected speech has
04700	also been studied here.  The published literature is behind in these
04800	fields and the questions may involve issues  raised in lectures or seminars.
04900	
05000		3.  Semantic Information Processing. General intelligence is
05100	closely related to the understanding of language.  Studies of semantic-
05200	information processes make use of the other areas of artificial intelligence,
05300	but have a distinct outlook.  The principal areas of concern are internal
05400	representations of semantics and the input and output of information in
05500	natural language.
05600	
05700		Most of the important work, up to a few years ago, is described
05800	in Minsky's Semantic Information Proecesing.  More recent trends include an
05900	increasing use of theorem proving techniques (18, 23) and the employment
06000	of more sophisticated linguistics (21, 22).
06100	
06200		4.  Representation Theory.  General intelligence requires a means
06300	of representing in the memory of the computer a picture of the world
06400	adequate for receiving problems and for constructing individual
06500	representations for them appropriate for their solution.  The development
06600	of a logically adequate general representation for situations involving
06700	action has been a subject of continuing interest (25, 26).  For more
06800	specific problems, one is concerned with representations which make
06900	problem solving more efficient.  Although the appropriate representation
07000	is often the key to solving a problem, there is no systematic
07100	understanding of how to choose representations, only sets of illustrative
07200	examples and like (24, 27).
07300	
07400	
07500	
07600		The examination will be open library and will be held on April 1,
07700	1972, between the hours of 10 a.m. and 5 p.m.; bring a lunch or buy it
07800	from the machines.
07900	
08000	
08100	
08200	I.  Heuristics
08300	
08400	*	1.	Buchanan, B., Sutherland, G., and Feigenbaum, E.A.,
08500			"Heuristic DENDRAL: A Program for Generating Explanatory
08600			Hypotheses in Organic Chemistry," Machine Intelligence
08700			4, Edinburgh University Press, 1969.
08800	
08900	**	2.	Ernst, G.W. and Newell, A., GPS: A Case Study in Generality
09000			and Problem Solving, Academic Press, 1969.
09100	
09200	*	3.	Greenblatt, R.D. et al, "The Greenblatt Chess Program,"
09300			Proceedings of the FJCC 1967, Anaheim, California, 1967.
09400	
09500	 	4.      Michie, D., Fleming, J.G. and Oldfield, J.V., "A
09600			Comparison of Heuristics, Interactive, and Unaided Methods
09700			of Solving a Shortest-Route Problem," Machine Intelligence
09800			3, (D. Michie, ed.) Edinburgh University Press, 1968.
09900	
10000	*	5.	Newell, A., "Heuristic Search: Ill Structured Problems,"
10100			Progress in Operations Research (Vol. 3), Wiley, 1969.
10200	
10300		6.	Nilsson, N.J., "Searching Problem Solving and Game Playing
10400			Trees for Minimal Cost Solutions," Proceedings of the IFIP
10500			68 Congress, Edinburgh, Scotland, 1968.
10600	
10700		7.	Pohl, I., "Bi-Directions and Heueristic Search in Path
10800			Problems," Stanford Computer Science Department report CS
10900			136 and SLAC Report No. 104, May 1969.
11000	
11100	*	8.	Samuel, A., "Studies in Machine Learning Using the Game
11200			of Checkers," Computers and Thought (E. Feigenbaum and
11300			J. Feldman, eds), McGraw-Hill, 1963.
11400	
11500		9.	Samuel, A., "Studies in Machine Learning Using the Game
11600			of Checkers II - Recent Progress," IBM Journal of Research
11700			and Development, 1967.
11800	
11900	       10.	Slagle, J.R. and Bursky, P., "Experiments with a Multipurpose,
12000			Theorem-Proving Heuristic Program," Journal of the ACM,
12100			Vol. 15, No. 1, 85-99, (1968).
12200	
12300	       11.	Waterman, D., "Generalization Learning Techniques for
12400			Automating the Learning of Heuristics," Stanford Artificial
12500			Intelligence Memo AIM-102, July 1969.
12600	
12700	
12800	II.  Perception and Control
12900	
13000	*      12.	Feldman, J.A., et at., "The Stanford Hand-Eye Project,"
13100			Proceedings of the International Joint Conference on
13200			Artificial Intelligence (IJCAI),  Washington, D.C., May
13300			1969.
13400	
13500	*      13.	Guzman, A., "Decomposition of a Visual Scene into Bodies,"
13600			Proceedings of the FJCC '68 (1968).
13700	
13800	*      14.	McCarthy, J., et al, "A Computer with Hands, Eyes and
13900			Ears," Proceedings of the FJCC '68 (1968).
14000	
14100	*      15.	Nilsson, N.J., "A Mobile Automaton: An Application of
14200			Artificial Intelligence Techniques," Proceedings of
14300			IJCAI, 1969.
14400	
14500	       16.	Roberts, L., "Machine Perception of Three Dimensional
14600			Solids," Optical and Electro-optical Processing of
14700			Information, MIT Press, 1965.
14800	
14900	
15000	III.  Semantic Information Processing
15100	
15200	*      17.	Colby, K.M. and Smith, D.C., "Dialogues between Humans
15300			and an Artificial Belief System," Proceedings of IJCAI,
15400			Washiington, D.C., 1969.
15500	
15600	*      18.	Green, C., "Application of Theorem Proving to Problem
15700			Solving," Proceedings IJCAI, Washington, D.C. 1969.
15800	
15900	*      19.	McCarthy, J., "Programs with Common Sense," Semantic
16000			Information Processing (M. Minsky, ed.) MIT Press, 1969.
16100	
16200	*      20.	Quillian, M.R., "Semantic Memory," Semantic Information
16300			Processing (M. Minsky, ed.) MIT Press, 1969.
16400	
16500	       21.	Schank, R.C. and Tesler, L.G., "A Conceptual Parser for
16600			Natural Language," Proceedings of IJCAI, Washington,
16700			D.C. 1969.
16800	
16900	*      22.	Simmons, R.F., "Natural Language Question-Answering
17000			Systems 1969," University of Texas Report TTN87,
17100			Austin, Texas, 1969.
17200	
17300	       23.	Waldinger, R.J. and Lee, R.C.T., "PROW: A Step Toward
17400			Automatic Program Writing," Proceedings of IJCAI,
17500			Washington, E.D. 1969.
17600	
17700	
17800	IV.  The Problem of Representation
17900	
18000	       24.	Amarel, S., "On the Representation of Problems and
18100			Goal-Directed Procedures for Computers," Communications
18200			of the American Society for Cybernetics, Vol. I, No. 2, 
18300			1969.
18400	
18500	       25.	McCarthy, J., "Situations, Actions and Causal Laws,"
18600			Stanford University AI Memo 2, 1963; also, section 7.2
18700			of Semantic Information Processing (M. Minsky, ed.) MIT
18800			Press, 1969.
18900	
19000	*      26.	McCarthy, J. and Hayes, P., "Some Philosophical Problems
19100			from the Standpoint of Artificial Intelligence," Machine
19200			Intelligence 4, (D. Michie, ed.) Edinburgh University
19300			Press, 1969.
19400	
19500	*      27.	Newell, A., "Limitations on the Current Stock of Ideas
19600			about Problem Solving," Electronic Information
19700			Handling (Dent and Taulbee, eds.), Spartan, 1965.
19800	
19900	       28.	Simon, H.A., The Sciences of the Artificial, MIT Press, 1969.
20000	
20100	
20200	V.  Other
20300	
20400	*      29.	Feigenbaum, E.A. "Artificial Intelligence: Themes in the
20500			Second Decade", Proceedings of the IFIP 68 Congress,
20600			Edinburgh, Scotland, 1968; also, Stanford Artificial
20700			Intelligence Project Memo AI-67, August 1968.
20800	
20900	       30.	Feldman, J.A., et al "Grammatical Complexity and Inference,"
21000			Stanford Computer Science Department Report CS 125,
21100			June 1969.
21200	
21300	*      31.	Minsky, M., "Steps Toward Artificial Intelligence,"
21400			Computers and Thought (E. Feigenbaum and J. Feldman, edc.)
21500			Mc-Graw Hill, 19663.
21600	
21700	
21800	
21900	*   =   worthy of special attention
22000	**  =   important but scan